package graph.base;

public class DepthFirstSearch {
    private boolean[] marked;
    // 想通顶点个数
    private int count;

    public DepthFirstSearch(Graph g, int s) {
        marked = new boolean[g.V()];
        dfs(g, s);
    }

    private void dfs(Graph g, int v) {
        marked[v] = true;
        // 获取当前顶点的相邻顶点
        for (Integer w : g.adj(v)) {
            // 如果当前未被搜索
            if (!marked[w]) {
                // 往深度遍历
                dfs(g, w);
            }
        }
        count++;

    }

    // 判断w顶点与s顶点是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return count;
    }
}
